/*
https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/
 */
public class Solution28 {
    public int strStr(String haystack, String needle) {
        if (needle.length()==0){
            return 0;
        }
        int[] f=new int[needle.length()];
        for (int i=1,j=0;i<needle.length();i++){
            while (j>0 && needle.charAt(i)!=needle.charAt(j)){
                j=f[j-1];
            }
            if (needle.charAt(i)==needle.charAt(j)){
                j++;
            }
            f[i]=j;
        }
        for (int i=0,j=0;i<haystack.length();i++){
            while (j>0 && haystack.charAt(i)!=needle.charAt(j)){
                j=f[j-1];
            }
            if (needle.charAt(j)==haystack.charAt(i)){
                j++;
            }
            if (j==needle.length()){
                return i-needle.length()+1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution28().strStr("mississippi","issip"));
    }
}
